#include <iostream>

using namespace std;
void Swap(int *x ,int *y)
{
    int tmp=*x;
    *x=*y;
    *y=tmp;

}
void Print(int *arr,int n)
{
  for(int i=0;i<=n-1;i++)
  {
      cout<<arr[i]<<' ';
  }
}

//void InsertSort(int* arr,int n)
//{
//
//    for(int i=0;i<=n-2;i++)//需要交换的次数
//    {
//        //交换的区间
//        int front=i;
//        int end=i+1;
//
//        while(end>0)
//        {
//            if(arr[front]>arr[end])//如果前面的元素比他大就交换
//            {
//                Swap(&arr[front--],&arr[end--]);
//            }
//            else
//            {
//                break;
//            }
//        }
//    }
//}

//void ShellSort(int *arr,int n)
//{
//    int gap=n/3;
//    while(gap)
//    {
//        for(int i=0;i<n-gap;i++)//待排序
//        {
//            int prev=i;
//            while(arr[prev]>arr[prev+gap]&&prev>=0)
//            {
//                Swap(&arr[prev],&arr[prev+gap]);
//                prev=prev-gap;
//            }
//        }
//        if(gap==1)
//        {
//            break;
//        }
//        gap=gap/3+1;//可能一些数除完为1导致死循环
//    }
//}
//int main(int argc, char *argv[])
//{
//    int arr[]={90, 64, 7 ,98 ,88 ,12 ,41 ,25, 16, 54,-1};
//
//    //InsertSort(arr,sizeof(arr)/sizeof(arr[0]));
//    ShellSort(arr,sizeof(arr)/sizeof(arr[0]));
//    Print(arr,sizeof(arr)/sizeof(arr[0]));
//}
//void ChoseSort(int *arr,int n)
//{
//
//for(int j =0;j<n-1;j+=2)
//{
//
//    int began=0;
//    int end=n-1;
//    int max=end;
//    int min=began;
//    for(int i=1;i<n-j  ;i++)
//    {
//        if(arr[min]>arr[i])
//        {
//            min=i;
//        }
//        if(arr[max]<arr[i])
//        {
//            max=i;
//        }
//
//    }
//    Swap(&arr[began++],&arr[min]);
//    Swap(&arr[end--],&arr[max]);
//}
//}



//int  Potholing(int *arr,int head ,int tail)//挖坑法
//{
////    int began=head;
////    int end=tail;
////    int key=arr[0];
////    while(began<end)
////    {
////        while(began<end&&arr[end]>=key)
////        {
////            end--;
////        }
////        arr[began]=arr[end];
////        while(began<end&&arr[began]<=key)
////        {
////            began++;
////        }
////        arr[end]=arr[began];
////    }
////    arr[end]=key;
////
////
////    return end;
////}
////int  hoare(int *arr,int head ,int tail)
////{
////    int began=head;
////    int end=tail;
////    int key=head;
////    while(began<end)
////    {
////        while(began<end&&arr[end]>=arr[key])//去找大的
////        {
////            end--;
////        }
////
////        while(began<end&&arr[began]<=arr[key])//去找小的
////        {
////            began++;
////        }
////        Swap(&arr[began],&arr[end]);
////    }
////    Swap(&arr[key],&arr[end]);
////    return end;
////}
////void FBPointer(int *arr,int n)
////{
////
////    int key=*arr;
////    int* prev=arr;
////    int* cur=arr+1;
////    while(n--)
////    {
////        if(*cur<key)
////        {
////            Swap(cur,prev++);
////        }
////
////        cur++;
////
////    }
////}
////void QuickSort(int *arr,int front ,int end)//控制区间
////{
////    //
////    if(front>=end)
////    {
////        return ;
////    }
////
////    int key=hoare(arr,front,end);
////    //区间[front key-1][key+1 end]
////    QuickSort(arr,front,key-1);
////    QuickSort(arr,key+1,end);
////
////}
////int main(int argc, char *argv[])
////{
////    //int arr[]={90, 64, 7 ,98 ,88 ,12 ,41 ,25, 16, 54,-1};
////    int arr[]={6,1,2,7,9,3,4,5,10,8};
////    //InsertSort(arr,sizeof(arr)/sizeof(arr[0]));
////    QuickSort(arr,0,sizeof(arr)/sizeof(arr[0])-1);
////    Print(arr,sizeof(arr)/sizeof(arr[0]));
////}
//
//void  Middle_key(int *arr,int front ,int middle,int end)
//{
//    if(arr[front]>arr[end])
//    {
//        if(arr[front]<arr[middle])
//        {
//            return;
//        }
//    }
//    else if(arr[end]>arr[front])
//    {
//        if(arr[end]<arr[middle])
//        {
//            Swap(&arr[end],&arr[end]);
//            return;
//        }
//    }
//    else
//    {
//        Swap(&arr[end],&arr[middle]);
//    }
//}

void RMergerSort(int *arr,int *sort,int front,int end )
{
    if(front>=end)
    {
          return;
    }
    int middle=(front+end)/2;
    RMergerSort(arr,sort,front,middle);
    RMergerSort(arr,sort,middle+1,end);

    int began1=front,end1=middle;
    int began2=middle+1,end2=end;

    int index=front;
    while(began1<=end1&&began2<=end2)
    {
        if(arr[began1]<arr[began2])
        {
            sort[index]=arr[began1++];
        }
        else
        {
            sort[index]=arr[began2++];
        }
        index++;
    }

    while(began1<=end1)
    {
        sort[index++]=arr[began1++];
    }

    while(began2<=end2)
    {
        sort[index++]=arr[began2++];
    }
    for(int i=0;i<=end;i++)
    {
        arr[i]=sort[i];
    }

}

void MergerSort(int *arr,int front,int end )
{
    int *sort=(int*)malloc(sizeof(int)*end);
    RMergerSort(arr,sort,front,end-1);

}
int main()
{
    //int arr[]={90, 64, 7 ,98 ,88 ,12 ,41 ,25, 16, 54,-1};
    int arr[]={10,6,7,1,3,9,4,2};
    MergerSort(arr,0,sizeof(arr)/sizeof(arr[0]));
    Print(arr,sizeof(arr)/sizeof(arr[0]));
}


extern"C"